/**
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

*/

/**
思路：
在之前的 剪枝条件1：用过的元素不能再使用之外，又添加了一个新的剪枝条件，也就是我们考虑重复部分思考的结果，
于是 剪枝条件2：当当前元素和前一个元素值相同（此处隐含这个元素的 index>0 ），并且前一个元素还没有被使用过的时候，我们要剪枝
*/
import java.util.*;
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int depth=nums.length;
        boolean visited[]=new boolean[depth];
        List<List<Integer>>  res=new ArrayList();
        List<Integer> list=new ArrayList();
        if(depth<=0){
            return res;
        }
        dfs(nums,0,depth,visited,list,res);
        return res;
    }
    public void dfs(int[]nums,int n,int depth,boolean[] visited,List<Integer> list,List<List<Integer>> res){
        if(depth==n){
            res.add(new ArrayList(list));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && !visited[i - 1]){ //这个if判断是精髓，也是和全排列1的主要区别
                continue;
            }
            if(visited[i] ){
                continue;
            }else{
                visited[i]=true;
                list.add(nums[i]);
                dfs(nums,n+1,depth,visited,list,res);
                visited[i]=false;
                list.remove(list.size()-1);
            }
        }
    }
}